A network is a group of objects, or nodes, connected to each other by links. Data, people, or supplies may be transported between the nodes in a network via the links. Examples of common networks include train stations connected by tracks, a community connected by roads, a communications network connected by wires, fiber optics or satellite links, a supply network connected by delivery routes, and logic gates connected by paths in an integrated circuit. In some networks, such as a ring network, there is only one path between nodes. In others, such as a mesh network, there may be several different paths between any two nodes in the network.
Many networks provide critical functions to business and governments. Should there be an interruption in a supply network, a business may fail to meet its contract obligations. A failure in a communications network may mean critical messages, such as those needed for directing air traffic, are lost. In these types of networks, it is desirable to have a mesh network with backup paths to connect nodes should a primary path fail. This is known as network resiliency. Resiliency ensures that communication between nodes is not interrupted by the failure of any one link between nodes. In some networks, uninterrupted communication is so important that more than one backup path is often desired to increase network resiliency.
Alternate routes, or backup paths, may be identified using methods such as the “shortest path” method, which calculates a diverse path between nodes in a network by minimizing the number of links first and total link distance between nodes second. However, traditional methods are not reliable when more than one backup path is desired. For example, in a network where desired network resiliency requires three diverse paths among nodes, traditional methods fail to calculate the desired number of paths up to 5% of the time. In many networks the failure to provide at least three diverse paths results in an unacceptable failure rate. Therefore there exists a need for a system that will identify multiple alternate paths for all node pairs in a network where traditional methods fail.